﻿#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
const int INF = 0x3f3f3f3f;
int maxProfit(vector<int>& prices)
{
    int n = prices.size();
    vector<vector<int>> f(n, vector<int>(3, -INF));
    auto g = f;

    // 初始化
    f[0][0] = -prices[0];
    g[0][0] = 0;
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
            g[i][j] = g[i - 1][j];
            if (j >= 1) // 如果该状态存在
            {
                g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
            }
        }
    }
    // 找到最后⼀⾏的最⼤值
    int ret = 0;
    for (int j = 0; j < 3; j++)
    {
        ret = max(ret, g[n - 1][j]);
    }
    return ret;
}

int main()
{
    vector<int> v = { 3,3,5,0,0,3,1,4 };

    maxProfit(v);
	return 0;
}